Homomorphic encryption is a form of encryption that allows (some) computations to be carried out on ciphertext, thus generating an encrypted result which, when decrypted, matches the result of operations performed on the plaintext. A fully homomorphic encryption scheme (FHE) allows a computer to receive encrypted data and perform arbitrarily chosen computations on that data while it remains encrypted, without requiring the use of a decryption key. This concept, originally called a privacy homomorphism, was introduced by Rivest, Adleman and Dertouzos in [RAD78], shortly after the development of RSA [RSA78]. Many known public-key cryptosystems, like RSA, support one operation (either addition or multiplication) of encrypted data; supporting both operations at the same time is a much more difficult problem, and until recently, all attempts at constructing fully homomorphic encryption schemes turned out to be insecure.
In the early 1990's, Fellows et al. [FK94] proposed a first algorithm, PolyCracker, which is capable of performing algebraic computations on encrypted data without revealing the encrypted information. However, several years later, the algorithm proved to be insecure and attempted modifications to make the algorithm secure were not successful.
In the late 1990's, a secure and efficient algorithm to encode messages (NTRU) was proposed by [HPS98]. The algorithm has the same ring homomorphic feature (defined further below) as PolyCracker, but only a few operations can be performed on the encrypted data. Specifically, only a few additions and no multiplications are allowed. This “leveled” feature comes from the fact that the algorithm is an “error” based one, so that only circuits which keep the noise very low can be applied to the encrypted data.
In his thesis [GeTh09], C. Gentry described the first construction of a fully homomorphic cryptosystem that supports both addition and multiplication. Gentry's general recipe that produces fully homomorphic encryption schemes consists of several steps. First, one considers a probabilistic homomorphic encryption scheme. A probabilistic scheme is an encryption scheme that assigns to each message several different ciphertexts. One way of obtaining probabilistic schemes is by constructing encryption algorithms that depend on certain random quantities, called errors. Such encryption schemes are also called error-based encryption schemes. In general, a homomorphic encryption scheme is somewhat homomorphic, that is it can “handle” (i.e. decrypt correctly) low-degree polynomials on the encrypted data. Next, one squashes the decryption algorithm such that it can be expressed by a low-degree polynomial supported by the scheme, in which case the scheme is called bootstrappable. Finally, Gentry describes a bootstrapping transformation that allows conversion of a boostrappable scheme into a fully homomorphic encryption scheme ([Ge11]). The bootstrapping transformation involves a recryption procedure in which the scheme's decryption algorithm is evaluated homomorphically. Gentry applied in [GeTh09] (see also [Ge09]) this general recipe to a GGH-type scheme [GGH97] over ideal lattices. A significant research effort has been devoted to increase the efficiency of the implementation of this scheme [GH11], [SV10].
The main building block in Gentry's construction, that is, the somewhat homomorphic encryption scheme, was based on the hardness of problems on ideal lattices. Starting with the seminal work of Z. Brakerski and V. Vaikuntanathan [BV11], a new generation of fully homomorphic encryption schemes were constructed. The security of these schemes is based on the learning with error (LWE) assumption (more generally on the ring learning with error (RLWE) assumption) that is known to be at least as hard as solving hard problems in general lattices [R05]. To obtain (leveled) fully homomorphic encryption schemes, the authors introduced the so-called re-linearization technique. In [BGV12], the construction is refined using a modulus-switching technique to obtain better efficiency.
Currently, perhaps the simplest (leveled) FHE scheme based on the learning with errors assumption is by Z. Brakerski [Br12]. The most recent achievement in this direction was obtained in [GSW13], where the authors were able to construct a simpler (leveled) FHE scheme based on the LWE assumption by removing the extensive and complicated step that involves the re-linearization procedure.
The current state of the art in terms of FHE implementation is represented by a recent software library (HElib) of S. Halevi and V. Shoup, available at https://github.com/shaih/HElib. HElib is an implementation of the RLWE encryption scheme described in [BGV12], along with many other optimizations [HS14a]. To achieve FHE, the authors implemented a new recryption procedure with running times around 6 minutes [HS14b]. The fact that bootstrapping takes such a large amount of time makes this implementation of FHE unattractive. Future work in this direction will focus on minimizing the running time of the FHE bootstrapping procedure [DM15].
There appears to be only a single example of a ring homomorphic encryption scheme (as defined below), provided by Grigoriev and Ponomarenko [GP04]. More precisely, they disclosed the use of the theory of group algebras to produce cryptosystems over any field of odd characteristic. Consequently, they explicitly mention that their method cannot produce FHE schemes. In addition, even in the odd characteristic case, they do not give a concrete description of those schemes. More precisely, the encryption algorithm is not described and is only assumed to exist.